class Solution {
public:
    int countArrangement(int N) {
        int res = 0;
        vector<int> vec;
        for(int i = 0; i < N; i++)
            vec.push_back(i+1);
        dfs(vec, vec, res);
        return res;
    }
    void dfs(vector<int> pos, vector<int> candidates, int& res) {
        if(pos.size() == 1)
        {
            if(valid(pos[0], candidates[0]))
            {
                res++;
            }
            return;
        }
        for(int i = 0; i < pos.size(); i++)
        {
            if(!valid(candidates[0], pos[i]))
                continue;
            int temp1 = candidates[0];
            int temp2 = pos[i];
            candidates.erase(candidates.begin());
            pos.erase(pos.begin() + i);
            dfs(pos, candidates, res);
            candidates.insert(candidates.begin(), temp1);
            pos.insert(pos.begin() + i, temp2);
        }
    }
    bool valid(int i, int j) {
        if((i%j)&&(j%i)) return false;
        else return true;
    }
};
